МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
«ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Я.П. Романчук
ДИСКРЕТНА МАТЕМАТИКА
Конспект лекцій
Розглянутий на засіданні кафедри АСУ
як навчальний посібник для студентів
базового напрямку 050101 «Комп’ютерні науки»
денної та заочної форм навчання (протокол № 1-10/11 від 31 серпня 2010 р.)
Львів − 2010
УДК 519.1+519.6
Я.П. Романчук. Дискретна математика: Конспект лекцій для студентів напряму комп’ютерні науки спеціальності Інформаційні управляючі системи та технології. – Львів: НУЛП, 2010. – 210 с.
У конспекті викладено теорію множин і відношень; алгебру логіки і алгебру логіки висловлень і предикатів, теорію графів, моделі алгоритмів і програм, формальні граматики й мови, основи теорії кодування та шифрування.
Кожен розділ складається з основних визначень, властивостей, операцій і теорем; має значну кількість розв’язаних і ілюстрованих прикладів з об’єктами дискретної природи; містить вправи для аудиторної та самостійної роботи студентів.
Конспект лекцій може бути корисним для студентів інших спеціальностей, які бажають вивчати методи дискретної математики для використання їх у природничих і гуманітарних науках із залученням інформаційних технологій.
Рецензент:
І.М. Дронюк, кандидат фізико-математичних наук, доцент кафедри АСУ.
Відповідальна за випуск:
З.Я. Шпак, кандидат технічних наук, доцент кафедри АСУ.
Лекція 2
3. ЛОГІКА ВИСЛОВЛЕНЬ
Логіка, як наука про закони людського мислення бере початок від грецького філософа Аристотеля. Ідеї побудови логіки на математичній основі вперше були запропоновані німецьким математиком Г. Лейбніцом. Пізніше англієць Д. Буль створив алгебру висловлень, у якій висловлення позначені буквами.
3.1. Основні означення.
Означення 3.1. Висловлення – це розповідне речення, про яке можна сказати, що воно істинне або хибне. Істинність або хибність, приписувані висловленню, називаються його істиннісним значенням.
Наприклад, речення «Сонце – це зірка», «Балаклава – обласний центр України», «Карась – не риба» є висловленнями, причому перше – істинне, а друге й третє – хибні. А речення «котра година?», «вивчіть вірш» не є висловленнями.
У математичних міркуваннях і повсякденній мові часто зустрічаються речення, що утворені видозміною деякого речення з використанням слова не, або складені із простих речень з використанням сполучників: і, або, якщо … то, тоді і тільки тоді, коли. Ці сполучники називаються сентенційними сполучниками. На відміну від повсякденної мови, у математичній логіці зміст таких висловлень може бути визначений однозначно.
Означення 3.2. Висловлення, що не містить сполучників, називається простим (елементарним); висловлення, що містить сполучники, називається складним.
Висловлення будемо позначати буквами латинського алфавіту , , , , , … . Розглянемо наступні прості висловлення:
«я прокидаюся рано»;
«я йду на роботу».
З використанням п’яти сентенційних сполучників можна утворити наступні складні висловлення:
заперечення – це речення, видозмінене з використанням слова не; воно позначається як , . Наприклад,
«я не прокидаюся рано»;
кон’юнкція – це речення, котре утворюється з’єднанням двох простих речень із використанням слова і; позначається як . Наприклад,
«я прокидаюся рано і йду на роботу»;
диз’юнкція це речення, що утворене з’єднанням двох простих речень з використанням слова або; вона позначається як . Наприклад,
«я прокидаюся рано або не йду на роботу»;
імплікація це речення, яке утворене з’єднанням двох простих речень з використанням слів якщо … то; позначається як . Наприклад, »
«якщо я прокидаюся рано, то йду на роботу»;
еквівалентність це речення, утворене з’єднанням двох простих речень з використанням слів тоді і тільки тоді, коли; позначається як . Наприклад,
«я прокидаюся рано тоді і тільки тоді, коли йду на роботу».
Означення 3.3. Символи називаються бінарними з’єднаннями, тому що вони з’єднують два висловлення, а символ ~ унарним з’єднанням, тому що застосовується тільки до одног...
